/*
 *  Optimized version of merge sort:
 *  1. cut off to sertion sort if length of array less than 8
 *  2. use auxiliary array
 *  3. skip merge if array is already sorted
 */
package algs4.sort;

public class MergeX
{
    /* Static Fields */
    private static final int CUTOFF = 8;

    /* Static Methods */
    public static void sort(Comparable[] a) {
        Comparable[] aux = a.clone();

        sort(a, aux, 0, a.length - 1);
    }

    public static void sort(Comparable[] a, int st, int ed) {
        Comparable[] aux = a.clone();

        sort(a, aux, st, ed);
    }

    // sort dst by src from st to ed
    private static void sort(Comparable[] dst, Comparable[] src, int st, int ed) {
        // base case
        if (ed < st + CUTOFF) {
            insertionSort(dst, st, ed);
            return;
        }

        int mid = (st + ed) / 2;

        sort(src, dst, st, mid);
        sort(src, dst, mid + 1, ed);

        // optimized
        if (src[mid].compareTo(src[mid+1]) <= 0) {
            System.arraycopy(src, st, dst, st, ed - st + 1);
            return;
        }

        merge(dst, src, st, mid, ed);
    }

    // merge src to dst
    private static void merge(Comparable[] dst, Comparable[] src, int st, int mid, int ed) {
        int i = st;
        int j = mid + 1;

        for (int k = st; k <= ed; k++) {
            if      (i > mid)                      dst[k] = src[j++];
            else if (j > ed)                       dst[k] = src[i++];
            else if (src[i].compareTo(src[j]) < 0) dst[k] = src[i++];
            else                                   dst[k] = src[j++];
        }
    }

    // insertion sort
    private static void insertionSort(Comparable[] a, int st, int ed) {
        for (int i = st + 1; i <= ed; i++) {
            int        j = i;
            Comparable v = a[i];

            for (; j > st && v.compareTo(a[j-1]) < 0; j--)
                a[j] = a[j-1];

            a[j] = v;
        }
    }
}
